package com.jiang.专题.字符串.Q5;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/11 21:31
 */
class Solution {
    public String longestPalindrome(String s) {
        // 中心扩散
        if (s == null || s.length() == 0) return "";
        int strLen = s.length(); // 字符串的长度
        int left = 0; // 回文子串的左侧
        int right = 0; // 回文子串的右侧
        int len = 1; // 回文子串的长度
        int maxLen = 0; // 最长回文子串的长度
        int startIndex = 0; // 最长回文子串的开始索引

        for (int i = 0; i < strLen; i++) {
            char c = s.charAt(i);
            left = i - 1;
            right = i + 1;
            // 向左扩散
            while (left >= 0 && s.charAt(left) == c) {
                len++;
                left--;
            }
            // 向右扩散
            while (right < strLen && s.charAt(right) == c) {
                len++;
                right++;
            }
            // 左右同时扩散
            while (left >= 0 && right < strLen && s.charAt(left) == s.charAt(right)) {
                len += 2;
                left--;
                right++;
            }
            if (len > maxLen) {
                maxLen = len;
                startIndex = left;
            }
            len = 1;
        }
        return s.substring(startIndex + 1, startIndex + maxLen + 1);

        // 动态规划
//        if (s == null || s.length() == 0) return "";
//        int strLen = s.length(); // 字符串的长度
//        int startIndex = 0; // 最长回文子串的开始索引
//        int maxLen = 1; // 最长回文子串的长度
//        boolean[][] dp = new boolean[strLen][strLen]; // 表示两字符简能否形成回文子串
//        for (int r = 1; r < strLen; r++) {
//            for (int l = 0; l < r; l++) {
//                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
//                    dp[l][r] = true;
//                    if (r - l + 1 > maxLen) {
//                        maxLen = r - l + 1;
//                        startIndex = l;
//                    }
//                }
//            }
//        }
//        return s.substring(startIndex, startIndex + maxLen);
//    }
    }
}